package tree;

import java.util.Arrays;

/**
 * 堆：完全二叉树,最大堆和最小堆，常用于优先队列（每次弹出最大或最小值），数组存储
 * 插入、删除时间复杂度为O(logN)
 *
 *  建堆两种方式：
 *     1.逐个插入法（向上调整）
 *
 */
public class HeapT {

    private int[] elem; // 存储堆元素的数组
    private int usedSize; // 堆中元素的数量

    // 构造函数，初始化堆的容量
    public HeapT(int maxSize) {
        this.elem = new int[maxSize];
        this.usedSize = 0;
    }

    public void batchHeap(int arr[]){
        for (int i = 0; i < arr.length; i++) {
            elem[i] = arr[i];
            usedSize++;
        }

        //从最后一个非叶子节点向下调整算法
        int last = (usedSize - 2 ) / 2;
        shiftDown(last);
    }

    //下沉操作
    public void shiftDown(int root){
        System.out.printf(String.valueOf(root));
        if( root < 0) return;
        int childIndex = 2 * root + 1;
        int cproot = root;
        while (childIndex < usedSize) {
           if(childIndex + 1 < usedSize && elem[childIndex] < elem[childIndex + 1]) {
               childIndex++;
           }
           if(elem[childIndex] > elem[cproot]) {
               swap(childIndex, cproot);
               cproot = childIndex;
               childIndex = 2 * cproot + 1;
           }else {
               break;
           }
        }
        shiftDown(root - 1);
    }


    //逐个插入法，也叫向上调整法,可建立最大堆和最小堆
    public void insert(int value) {
        elem[usedSize] = value;
        //上浮操作
        shiftUp();
        usedSize++;
    }

    //向上调整法
    public void shiftUp(){
        int curParentIndx = (usedSize - 1 ) / 2;
        int childIndex = usedSize;
        while (curParentIndx >= 0){
            if(elem[curParentIndx] > elem[childIndex]){
                swap(curParentIndx, childIndex);
                childIndex = curParentIndx;
                curParentIndx = (curParentIndx - 1) / 2;
            }else{
                break;
            }

        }
    }

    //交换元素
    public void swap(int i, int j){
        int temp = elem[i];
        elem[i] = elem[j];
        elem[j] = temp;
    }



    public static void main(String[] args) {
        int heap[] = {3,1,6,5,2,4};
        HeapT heapT = new HeapT(10);
        heapT.batchHeap(heap);
        System.out.println("Heap array: " + Arrays.toString(heapT.elem));

    }
}
